<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>Title</title>
</head>
<body>
<p>
  快速排序：

  复杂度 O(nlogn)
</p>

<script>
  function quickSort (arr) {
    if (arr.length <= 1) return arr

    const temp = arr[0]
    arr = arr.slice(1)
    const left = []
    const right = []
    for (let i = 0; i < arr.length; i ++) {
      if (arr[i] <= temp) {
        left.push(arr[i])
      } else {
        right.push(arr[i])
      }
    }
    return quickSort(left).concat(temp).concat(quickSort(right))
  }

  console.log(quickSort([9, 5, 3, 4, 100, 2, 1]))
</script>
</body>
</html>
